package com.squirrel.michale;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/3/13 8:09 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2439 {

    public int minimizeArrayValue(int[] nums) {
        int left = 0, right = 1000000000;
        while (left < right) {
            //二分答案，寻找最大值
            int mid = left + (right - left) / 2;
            if (check(nums, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    boolean check(int[] nums, int k) {
        long have = 0;
        //前方的数字还可以帮我们后方的大数承载多少数字
        for (int n : nums) {
            if (n <= k) {
                have += k - n;
                //较小数，可以算入承载量
            } else {
                if (have < n - k) return false;
                //承载不了了，该答案不可行
                else have -= (n - k);
                //减去承载量
            }
        }
        return true;
    }

//    作者：全力以赴✨
//    链接：https://leetcode.cn/problems/minimize-maximum-of-array/solutions/1894993/cppjava-you-shi-yi-dao-jing-dian-de-er-f-w3i6/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
